Szymanski's conjecture

Routing a permutation of the doubly-directed cube graph

In mathematics, Szymanski's conjecture, named after Ted H. Szymanski (1989), states that every permutation on the n-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is, if the permutation σ matches each vertex v to another vertex σ(v), then for each v there exists a path in the hypercube graph from v to σ(v) such that no two paths for two different vertices u and v use the same edge in the same direction.

Through computer experiments it has been verified that the conjecture is true for n ≤ 4 (Baudon, Fertin & Havel 2001). Although the conjecture remains open for n ≥ 5, in this case there exist permutations that require the use of paths that are not shortest paths in order to be routed (Lubiw 1990).

References

• Baudon, Olivier; Fertin, Guillaume; Havel, Ivan (2001), "Routing permutations and 2-1 routing requests in the hypercube", Discrete Applied Mathematics, 113 (1): 43–58, doi:10.1016/S0166-218X(00)00386-3.
• Lubiw, Anna (1990), "Counterexample to a conjecture of Szymanski on hypercube routing", Information Processing Letters, 35 (2): 57–61, doi:10.1016/0020-0190(90)90106-8.
• Szymanski, Ted H. (1989), "On the Permutation Capability of a Circuit-Switched Hypercube", Proc. Internat. Conf. on Parallel Processing, vol. 1, Silver Spring, MD: IEEE Computer Society Press, pp. 103–110.